//class Solution {
//public:
//    bool Travel(stack<TreeNode*>& s, TreeNode* root, TreeNode* x) {
//        if (root == nullptr) {
//            return false;
//        }
//        s.push(root);
//        if (root == x) {
//            return true;
//        }
//        if (Travel(s, root->left, x)) {
//            return true;
//        }
//        if (Travel(s, root->right, x)) {
//            return true;
//        }
//        s.pop();
//        return false;
//    }
//    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//        stack<TreeNode*> ps;
//        stack<TreeNode*> qs;
//        Travel(ps, root, p);
//        Travel(qs, root, q);
//        while (ps.top() != qs.top()) {
//            if (ps.size() > qs.size()) {
//                ps.pop();
//            }
//            else if (ps.size() < qs.size()) {
//                qs.pop();
//            }
//            else {
//                qs.pop();
//                ps.pop();
//            }
//        }
//        return ps.top();
//    }
//};

//class Solution {
//public:
//	void Inorder(TreeNode* root, TreeNode*& x) {
//		if (root == nullptr) {
//			return;
//		}
//		Inorder(root->left, x);
//		if (x) {
//			root->left = x;
//			x->right = root;
//		}
//		x = root;
//		Inorder(root->right, x);
//	}
//	TreeNode* Convert(TreeNode* pRootOfTree) {
//		if (pRootOfTree == nullptr) {
//			return nullptr;
//		}
//		TreeNode* p = nullptr;
//		Inorder(pRootOfTree, p);
//		TreeNode* head = pRootOfTree;
//		while (head->left) {
//			head = head->left;
//		}
//		return head;
//	}
//};